﻿#define  _CRT_SECURE_NO_WARNINGS 1

//使用最小花费爬楼梯
//给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
//你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
//请你计算并返回达到楼梯顶部的最低花费。


//dp[i]：  到达dp[i]位置的最小花费
//min((cost[i - 1] + dp[i - 1]), (cost[i - 2] + dp[i - 2]))
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int high = cost.size();
        if (high == 2)return min(cost[0], cost[1]);

        vector<int> dp(high + 1, 0);
        for (int i = 2; i <= high; ++i)
        {
            dp[i] = min((cost[i - 1] + dp[i - 1]), (cost[i - 2] + dp[i - 2]));
        }
        return dp[high];
    }
};
//dp[i] 表⽰：从 i 位置出发，到达楼顶，此时的最⼩花费。
//cost[i] + min(dp[i + 1], dp[i + 2]);
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];
        for (int i = n - 3; i >= 0; --i)
        {
            dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
        }
        return min(dp[0], dp[1]);
    }
};


//解码方法
// 
//dp[i]: 以i结尾时的解码数
//单独解码 成功 = dp[i-1]  失败 0
//和上一个一起解码 成功 = dp[i-2] 失败 0
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = s[0] != '0';

        for (int i = 2; i <= n; ++i)
        {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            int t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (t >= 10 && t <= 26)dp[i] += dp[i - 2];
        }

        return dp[n];
    }
};